import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int [] arr = {1,2,5,4,9,6};
        Test.heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    // 插入排序
    public static void insertSort(int[] array){

        for (int i = 1; i < array.length; i++) {
            int j= i-1;
            int emp = array[i];
            for (;j >=0; j--) {
                if ( array[j] >= emp) {
                    array[j+1] = array[j];// j位置的值比emp大 向后移动
                }
                else{
                    break;
                }
            }
            array[j+1] = emp;
        }
    }

        // 希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            gap /=2;
            shell(gap,array);
        }
    }
    public static void  shell (int gap,int[] array){
        for (int i = gap; i < array.length; i++) {
            int j = i-gap;
            int tep = array[i];
            for (;  j>= 0; j-=gap) {
                if (array[j] > tep) {
                    array[j+gap] = array[j];
                }
                else {
                    break;
                }
            }
            array[j+gap] = tep;
        }
    }
    // 选择排序
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < min) {
                    min = j;
                }
            }
            sw(array,i,min);
        }
    }
    private static void  sw (int [] array,int i , int min){
        int tep = array[i];
        array[i] = array[min];
        array[min] = tep;
    }


    // 堆排序
    public static void heapSort(int[] array){
        creatHeap(array);
        int end = array.length-1;
        while (end > 0){
            sw(array,0,end);
            siDown(0,end,array);
            end--;
        }
    }
    public  static  void  creatHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >= 0;parent--) {
            siDown(parent,array.length,array);
        }
    }
    public static void siDown(int parent,int length,int[] array){
        int chile =2*parent+1;
        while (chile < length){
            if (chile+1 < length && array[chile] < array[chile+1]){
                chile++;
            }
            if (array[chile] > array[parent]) {
                sw(array,chile,parent);
                parent = chile;
                chile = 2*parent+1;
            }else {
                break;
            }
        }
    }
    // 冒泡排序
public static void bubbleSort(int[] array){
    for (int i = 0; i < array.length-1; i++) {
        boolean flg = false;
        for (int j = 0; j < array.length-1-i; j++) {
            if (array[j] > array[j+1]){
                sw(array,j,j+1);
                flg = true;
            }
        }
        if (!flg){
            break;
        }
    }
    }

// 快速
public static void quickSort(int[] array){
       quock(array,0,array.length-1);
    }

    private static void quock(int[] array, int star, int end) {
        if (star >= end) {
            return;
        }
        int in = infind(array,star,end);
        quock(array,star,in-1);
        quock(array,in+1,end);
    }

    private static int infind(int[] array, int left, int right) {
        int tep = array[left];
        int i = left;
        while (left < right){
            if (left < right && array[right] >= tep) {
                right--;
            }
            if (left < right && array[left] <= tep) {
                left++;
            }
            sw(array,left,right);
        }
        sw(array,i,left);
        return left;
    }
}
